<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>Balanced-tree</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">平衡树及其应用</h1>
<h4 id="toc-1">什么是平衡树？</h4>
<hr>
<p>顾名思义，是一种平衡的树。</p>
<p>蛤蛤蛤</p>
<p>以上都是瞎基本loupi</p>
<hr>
<p>首先需要申明一个概念：二叉搜索树。</p>
<h4 id="toc-2">二叉搜索树：</h4>
<p>二叉搜索树是一种十分神奇的树，也可以叫做二叉排序树、二叉查找树。</p>
<p>一个牛逼的性质：（多数情况下，也有例外）</p>
<p>对二叉搜索树而言，若它非空，每个节点的左儿子总是比他小，每个节点的右儿子总是比他大。</p>
<p>对于二叉搜索树的查找而言，是靠递归调用实现的，<strong>期望</strong>的时间复杂度是：</p>
<p>[O(nlogn)]</p>
<p>那么就一定会有特殊情况，比如当数据很诡异的时候，这颗树就会退化成一条链，那么处理的时间复杂度就会变成：</p>
<p>[O(n)]</p>
<p>所有我们在这个的基础上，就有了平衡树的概念。</p>
<h2 id="toc-3">平衡树的分类</h2>
<p><strong>一、treap</strong></p>
<p><strong>二、splay</strong></p>
<p><strong>三、RBT（红黑树）</strong></p>
<p><strong>四、AVL</strong></p>
<p>是的以上四个，在本篇笔记中会涉及前两个，并且很草率地给出几段代码，以及浅显的涉及一下三和四。</p>
<hr>
<p>在一般的二叉搜索树当中，如果退化换成了一条链，那对于所写的数据结构而言没有任何时间和代码量的优势。</p>
<p>所以在这个二叉搜索树上维护一个堆，是的，维护一个Heap。</p>
<p>[ Tree + Heap= Treap ]</p>
<h3 id="toc-4">一、Treap</h3>
<p>Treap是一种平衡树，但是他自己首先也是一颗二叉搜索树，其左子树和右子树也均为一个Treap。</p>
<p>Treap在一般二叉搜索树的基础上，还额外记录了一个数据，即为优先级。（假设节点的优先级大于该节点的孩子的优先级）
值得一提的是，对于Treap而言，它是一颗二叉搜索树，但是不一定是一个完全二叉树。与二叉堆不同。</p>
<h4 id="toc-5">Treap的各种操作</h4>
<p><strong>一、插入一个数K</strong></p>
<p>因为满足二叉排序树，所以我们可以从根节点开始往下查找，每找到一个节点 O，会有如下四种情况：</p>
<p>1、O 为空，那就创建新节点，初始化，赋值key、pri。</p>
<p>2、k == O.key 那么直接把 O.val + 1 即可。</p>
<p>3、k小于当前节点的key值，那就进入该节点的左儿子找。</p>
<p>4、k大于就去右边哇QwQ</p>
<p>但是简单的加完之后还要满足Treap的性质，所以我们还需要考虑在当前情况不满足堆的性质的时候的操作。</p>
<p><strong>因为维护的堆性质不同，所以操作也不一样，维护大根堆和维护小根堆的操作相反。</strong></p>
<h4 id="toc-6">旋转</h4>
<p>左旋or右旋</p>
<p><img src="http://ww2.sinaimg.cn/large/0060lm7Tly1fjo4hi73jij30x80cm74m.jpg" alt="image"></p>
<p>从左边到右边的就是左旋，反之就是右旋。
经过观察可知，在旋转前后，这一部分的中序遍历均为BADCE，即旋转不破坏二叉排序树的性质，所以我们维护这个Treap的方式就是旋转啦。</p>
<p>我们首先来分析一下时间复杂度，旋转的操作是O（1）的，最多进行H次操作，所以插入的时间复杂度就是O（H）的，在期望的情况下H=O（logn），所以它的<strong>期望</strong>复杂度就是O（logn）。</p>
<p>回顾一下刚才的那个图，核心的节点是A和C，旋转时只需要调整节点D的位置，再调整A、C的父子关系，最后再维护完val和size。</p>
<p>再创建完新的节点之后，可以得到根节点到这个新节点的一条路径，递归回溯时，对这条路径上 的每两个点：将优先级大的放到父节点上去。看节点在左还是在右，就知道是进行左旋还是右旋。</p>
<p>原图
<img src="http://ww4.sinaimg.cn/large/0060lm7Tly1fjo51c3kgfj312t0t5my4.jpg" alt="image"></p>
<p>插入C-25
<img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjo4vllbuej312q0t50ts.jpg" alt="image">
插入D-9
<img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjo4vlmzxuj312q10qmyg.jpg" alt="image">
左旋
<img src="http://ww4.sinaimg.cn/large/0060lm7Tly1fjo4vln62yj312q10t75k.jpg" alt="image">
右旋
<img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjo52e5yi2j312l0t4mzp.jpg" alt="image">
插入F-2
<img src="http://ww1.sinaimg.cn/large/0060lm7Tly1fjo532u0htj312n10m75n.jpg" alt="image">
左旋
<img src="http://ww2.sinaimg.cn/large/0060lm7Tly1fjo4vll9cij312t10qdh7.jpg" alt="image">
左旋
<img src="http://ww1.sinaimg.cn/large/0060lm7Tly1fjo4vm4eeyj312q10njsr.jpg" alt="image">
左旋
<img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjo4vlnri9j318310qdhb.jpg" alt="image">
右旋
<img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjo4vmc0h9j318310qmyn.jpg" alt="image"></p>
<p><strong>二、删除一个数K</strong></p>
<p>因为Treap满足了堆的性质，所以当要删除的点在叶子节点的话直接删除就可以了，至于不在叶子节点的节点，需要找到优先级最大的儿子，像相反的方向旋转（既让优先级大的儿子至于尽可能高的位置）当要删除的借点</p>
<p>删除最多进行 O（H）次旋转，<strong>期望</strong>复杂度是 O (log n)</p>
<p><strong>三、查询数K的排名</strong></p>
<p>从根节点开始往下找，判断当前节点的key值。</p>
<p>大于K就继续向当前节点的左节点去找。</p>
<p>等于K就返回当前节点的左子树的size值+1。</p>
<p>小于K就先把答案加上当前节点的左子树的size值以及当前这个点的val值（val个相等的值）之后一点一点往下找就行啦QAQ。</p>
<p>因为Treap是随机化结构，所以可以证明Treap中查找的<strong>期望</strong>复杂度是 O （logn）</p>
<p><strong>四、查询排名为K的数</strong></p>
<p>与第三个类似，递归查询。</p>
<p>K小于当前节点的左子树的大小，向左子树去找。</p>
<p>当K大于左子树的大小却小于左子树的大小+当前节点的val时，那么就说明该节点的key就是答案。</p>
<p>若K大于左子树的大小+当前节点的val时，向右边去找就可以了，但是K在向下递归的时候，需要减去左子树的大小和val</p>
<p><strong>五、查询数K的前驱</strong></p>
<p>前驱：在一段有序的序列里面最后一个比K小的数。</p>
<p>首先，因为是最后一个比K小的数，所以这个数一定在K的左子树上面，找到左子树就要向右子树啦，因为要保证尽可能的大，更新答案，答案赋一个极小值。</p>
<p><strong>六、查询数K的后继</strong></p>
<p>后继：在一段有序的序列里面第一个比K大的数</p>
<p>与操作五正好相反。QAQ</p>
<hr>
<p>举个栗子：</p>
<p><strong>bzoj3224普通平衡树</strong></p>
<p><a href="http://www.lydsy.com/JudgeOnline/problem.php?id=3224">bzoj3224普通平衡树</a></p>
<p>题意：写一个具有插入、删除、查rank、求前驱、后继功能的平衡树。 N&lt;=100000。</p>
<p>一句话题解:纯模板，记得在左旋右旋和insert中加取地址符，这个叫做引用，在子程序中改变该变量的值会导致主程序中该变量的值发生改变，类似将局部变量局部地拓展到某一个子程序中，变成一个类全局变量。</p>
<p><a href="http://paste.ubuntu.com/25576538/">code</a></p>
<hr>
<p>Another：</p>
<p><strong>bzoj3173最长上升子序列</strong></p>
<p><a href="http://www.lydsy.com/JudgeOnline/problem.php?id=3173">bzoj3173最长上升子序列</a></p>
<p>题意：给定一个空序列，将1——N数字插入序列中，给定插入的位置，每插入一个值求lis。N&lt;=100000。</p>
<p>一句话题解：正常的平衡树维护一个lis，根据其中序遍历求这些lis，用dfs把中序遍历存在一个数组中，跑一次lis，存在数组里，然后输出N个局部最大就是答案啦。</p>
<p><a href="http://paste.ubuntu.com/25572689/">code</a></p>
<hr>
<h3 id="toc-7">二、Splay</h3>
<p>Splay又称为伸展树，是对于二叉搜索树的一种改进，和二叉搜索树一样，伸展树也具有<strong>有序性</strong>。对于一个节点x，左子树的每一个元素都小于x，右子树的每一个元素都大于x，同时Splay也具有其本身的旋转操作，多数为双旋，并且双旋的速度会优于单旋。</p>
<h4 id="toc-8">旋转：</h4>
<p>zig：右旋。</p>
<p>zag：左旋。</p>
<p>将旋转组合一下，会得到奇特的效果</p>
<p>比如zig-zig</p>
<p><img src="http://ww3.sinaimg.cn/large/0060lm7Tly1fjp94ubplgj30a704aa9z.jpg" alt="图片"></p>
<p>第一次zig，g成了p的右儿子，p的右儿子继承给了g，g成了根，g的左子树不变。</p>
<p>第二次zig，x成了根，p成了根的右儿子，所以p就继承了x的右儿子，p的右子树不变</p>
<p>至于zag-zag与上图类似。</p>
<p>着重讲一下复合旋转。</p>
<p><img src="http://ww4.sinaimg.cn/large/0060lm7Tly1fjp9b2nab4j30bu050dfs.jpg" alt="image"></p>
<p>例如这个图，就需要zag-zig</p>
<p>首先zag一下，就成了一条链，p的右儿子继承了x的左儿子，c不变，a不变。</p>
<p>再zig一下，就变成了第二个图的样子。</p>
<p><strong>特别重要的一点就是在旋转中他的中序遍历是不变的</strong></p>
<p>如何快速判断这个中序遍历是啥？把这个树压扁然后就可以看到，两个节点中间的点仍然在两个节点中间。</p>
<p>zig-zag与zag-zig是不一样的！！</p>
<h4 id="toc-9">多种操作</h4>
<p><strong>查找第K大的数</strong></p>
<p>首要的是要把标记下传，因为每次传标记可能还没有传到叶子结点，然后再判断当前这个点和当前这个节点的左子树大小的关系。往下找就行了</p>
<p><strong>旋转某个点到某个点</strong></p>
<p>首先下传标记，然后要不断的旋转，保证这个点到了要旋转到的点才停止，找到三层关系，之字型就符合复合旋转的操作，链式就是符合多次相同方向的旋转的操作</p>
<p><strong>^</strong> 就是两边相同就是真，相反就是假，59行的if就是判断他是不是之字形操作</p>
<p>之字形就是两次rotate（o,x）。
链形就是一次rotate（o,y）,一次rotate（o,x）。</p>
<p>在rotate里面穿进去的x或者y意思就是，把x节点或者y节点由下移到上去。</p>
<p><strong>rotate</strong></p>
<p>首先要把这个点三层关系找到，自己父亲爷爷，看看他们是不是全在各自的右节点的位置，如果都为0那就都在左节点的位置上，都为1就都在右，有0有1就表示是之字形的关系，然后下传标记</p>
<p>如果要移动到的点刚好是这个点的父亲节点，就直接移动。</p>
<p>不然就去分析其左右节点关系和继承儿子的关系，因为有 ^ 的存在，所以只用判断 ^ 的结果就好了</p>
<p><strong>pushdown</strong></p>
<p>如果当前节点的rev存在，就旋转左右子树即翻转左右区间。同时标记还要下传。</p>
<p><strong>reverse</strong></p>
<p>就是交换左右子树，即交换翻转区间</p>
<p><strong>pushup</strong></p>
<p>总结左右儿子的大小并且还要加上自身的一个</p>
<p><strong>print</strong></p>
<p>以其中序遍历输出，记得判断o得在[l,r]区间输出</p>
<p><a href="http://paste.ubuntu.com/25577547/">code</a></p>
<h3 id="toc-10">三、RBT</h3>
<p>一、每个节点要么是红的，要么是黑的</p>
<p>二、根节点为黑</p>
<p>三、叶子结点为黑</p>
<p>四、若自身为红，则左右儿子为黑</p>
<p>五、每一个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点</p>
<p>六、红色节点向左倾斜</p>
<p>RBT有较多版本，一些为链为红或者黑，还有一些为点为红或者黑，但是红黑树是一种具有两种颜色的平衡查找树</p>
<p>旋转与Treap的旋转一样，但是颜色会出现一个翻转=。=然后就不会啦QAQ</p>
<p><a href="http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html">红黑树博客</a></p>
<h3 id="toc-11">四、AVL树</h3>
<p>特点：任何节点的两个子树的高度最大差别为1，但是对于AVL树而言有4种旋转方式，对应的是AVL树的四种情况，有LL、LR、RR、RL四种，因为最大高度差不能大于1，所以会有不平衡，然后对应起来去转就可以了QAQ后面我也不会啦</p>
<p><a href="http://www.cnblogs.com/skywang12345/p/3576969.html">AVL树博客</a></p>
<h4 id="toc-12">最后再说几句</h4>
<p>平衡树花了3天多的时间，真的是好费劲啊，但是一个算法都不想放下，时间不够用啊，好紧张啊！！！！！！
<strong>IOI</strong>选手加油啊</p>
<h2 id="toc-13">By：Wahacer</h2>
<h2 id="toc-14">资料来源</h2>
<p>Treap：xqmmcqs——数据结构-Treap</p>
<p>Splay：IOI2004 国家集训队论文 杨思雨</p>
<p>RBT：结构之法算法之道blog之博主</p>
<p>AVL：AVL树(一)之 图文解析 和 C语言的实现</p>
<h2 id="toc-15">特别鸣谢：uncle-lu、xqmmcqs、杨思雨</h2>
<p>2017年9月20号</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>